package main.leetcode.clockin.March;

/**
 * 1071.字符串的最大公因子
 *
 * <p>对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
 *
 * <p>返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
 *
 * <p>
 *
 * <p>示例 1：输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
 *
 * <p>示例 2：输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
 *
 * <p>示例 3：输入：str1 = "LEET", str2 = "CODE" 输出：""
 *
 * <p>提示：1 <= str1.length <= 1000，1 <= str2.length <= 1000，str1[i] 和 str2[i] 为大写英文字母
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day12 {
    public static void main(String[] args) {
        String str1 = "ab";
        System.out.println(str1.indexOf("abab"));
    }

    // 辗转相除法（我可真他妈的菜
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) return ""; // 正反相等才说明两者都有公因子
        return str1.substring(
                0, gcd(str1.length(), str2.length())); // 辗转相除求最大公因子，前缀一定是最大公因子，可以直接从前缀开始找
    }

    // ababab--6 ab--2
    // ab--2 --0
    private int gcd(int n1, int n2) {
        return n2 == 0 ? n1 : gcd(n2, n1 % n2);
    }
}
